#pragma once
#include <iostream>
#include <vector>
#include <queue>

template<class W>
struct HuffmanTreeNode
{
	HuffmanTreeNode<W>* _left;
	HuffmanTreeNode<W>* _right;
	HuffmanTreeNode<W>* _parent;
	W _weight;
	HuffmanTreeNode(const W& weight = W())
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _weight(weight)
	{}
};

template<class W>
class HuffmanTree
{
	typedef HuffmanTreeNode<W> Node;

	class Compare
	{
	public:
		bool operator()(const Node* x, const Node* y)
		{
			return x->_weight > y->_weight;
		}

	};

public:
	HuffmanTree()
		: _root(nullptr)
	{}
	HuffmanTree(const std::vector<W>& vw, const W& invalid)
	{
		std::priority_queue < Node*, std::vector<Node*>, Compare > q;
		for (auto& e : vw)
		{
			if (invalid != e)
			{
				q.push(new Node(e));
			}
		}

		while (q.size() > 1)
		{
			Node* left = q.top();
			q.pop();

			Node* right = q.top();
			q.pop();

			Node* parent = new Node(left->_weight + right->_weight);
			parent->_left = left;
			left->_parent = parent;

			parent->_right = right;
			right->_parent = parent;

			q.push(parent);
		}

		_root = q.top();
	}

	~HuffmanTree()
	{
		Destroy(_root);
	}

	Node* GetRoot()
	{
		return _root;
	}
private:
	void Destroy(Node*& root)
	{
		if (root)
		{
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
	}

private:
	Node* _root;
};

